1. Field of the Invention
The present invention relates to computerized image processing and more particularly to determining the skew angle of an original bitmap image and de-skewing and auto-copping the bitmap image.
2. Description of the Related Art
A raster or bitmap image is usually represented in a digital image processing system by a rectangular grid of pixels, where the pixel is a basic discrete unit for defining bitmap images and has a defined location and color value. A 24 bit digital image system may be defined by three channels comprising of Red (R), Green(G) and Blue (B), where each channel of color contains 8 bits of information with a range of 0 to 255. However, the image is sometimes skewed or misaligned with respect to the rectangular grid. This may occur during the scanning process, which converts physical scenes or images into binary information and thereby links a physical image to a digital computer system. The bitmap image will be skewed if the original image is skewed relative to the scanner platen or when the image is misfed, during the scanning process.
Another way that the bitmap image might be skewed relative to the grid of pixels is where, the original image itself is skewed with respect to the paper. This may occur if the image is photocopied onto to a sheet of paper, which is later used for scanning. The image gets skewed during the photocopying process and hence remains skewed after scanning. FIG. 3a provides an example of a perfectly aligned bitmap image in which 101 is the rectangular grid of pixels, and 102 are pixels representing bitmap image data of an original image and FIG. 3b shows a skewed bitmap image as 103.
Another related problem is presence of background pixels with the image pixels, after an image is scanned as shown in FIG. 3a or 3b. This occurs when the image is copied on a sheet of paper and occupies a smaller area than the sheet itself. The scanner scans the entire sheet and the resulting bitmap image then has both image and background pixels. A user may not need the background pixels and hence there is a need to crop the scanned image.
Various techniques have been proposed for determining a skew angle, de-skewing and auto-cropping a bitmap image, which is comprised of both background and image pixels. However, each has its own problems and limitations. For example, some conventional techniques are computationally intensive, while others work well only with certain types of images, such as a text image, but not with other type of images. Some others correct only errors where the entire image is skewed relative to the grid and not to the paper itself. Others only straighten the image and fail to auto-crop the image from the background pixels. Hence there is a need to straighten the skewed bitmap image as well as auto-crop the image area from the background, so that a user can process a straight image without excessive background pixels.
It is one object of the present invention to address the disadvantages found in conventional techniques for determining a skew angle of a bitmap image and de-skeweing the bitmap image by the determined skew angle, and to address these disadvantages by determining a bitmap image skew angle by a simple process which is not taxing on computer performance and is independent of image type.
It is another object of the invention to provide an auto-cropping technique which automatically auto-crops a bitmap image, by a process which is accurate and is not computationally intensive.
In one aspect, the invention is the determination of a bitmap image skew angle, where the bitmap image is comprised of background and image pixels. The bitmap image skew angle is determined by calculating a first estimate of the skew angle for a first side of the bitmap image and a corresponding first reliability indicator, the first estimate of the skew angle being based upon the position of image pixels closest to the first side at a plurality of positions along the first side. Thereafter, a second estimate of the skew angle is calculated for the second side with a corresponding second reliability indicator. The second estimate of the skew angle is based upon the position of image pixels closest to the second side at a plurality of positions along the second side. Finally, the bitmap image skew angle is determined in accordance with which of the first and second has the better reliability indicator and the bitmap image may be de-skewed by the determined skew angle.
The first estimate of the skew angle may be determined by calculating a first set of plural angles by inverse tangent, based upon the positions of the image pixels closest to the first side at a plurality of positions along the first side. Thereafter, a mean of the first set of plural angles is calculated as the first estimate of the bitmap image skew angle. Furthermore, a first standard deviation of the first set of plural angles is calculated, wherein the first standard deviation is the reliability indicator for the first estimate of the skew angle.
Similarly, the second estimate of the skew may be determined by calculating a second set of plural angles by inverse tangent, based upon the positions of the image pixels closest to the second side at a plurality of positions along the second side. A mean of the second set of plural angles is calculated and is the second estimate of the bitmap image skew angle, and then a second standard deviation of the second set of plural angles is calculated, wherein the second standard deviation is the reliability indicator for the second estimate of the skew angle.
The least standard deviation from among the first and second standard deviation is the best reliability indicator and the mean angle corresponding to the least standard deviation is chosen as the bitmap image skew angle. It is noteworthy that instead of using the mean angle corresponding to the best reliability indicator, the minimum angle among the first or second set of plural angles, corresponding to the least standard deviation may be chosen as the bitmap image skew angle.
As described above, instead of only using the first and second estimates of the bitmap image skew angles, a third and fourth estimate of the skew angle may also be used, along with the first and second estimates. The third and fourth estimates are based upon the position of image pixels closest to the third and fourth side respectively, at a plurality of positions and have corresponding third and fourth reliability indicators. The third and fourth estimates of the bitmap image skew angle are determined by calculating a third and fourth set of plural angles by inverse tangent and thereafter by calculating a mean of the third and fourth set of plural angles. The third and fourth reliability indicators are determined by calculating the standard deviations of the third and fourth set of plural angles.
The plural estimates of the bitmap skew angle may also be determined by obtaining plural set of points encountered when a set of parallel lines are traversed in a defined direction from background to image pixels. The set of points provide plural set of angles derived from the set of points, wherein the plural angles may be calculated by inverse tangent and estimates of reliability may be based upon standard deviations of the plural set of angles. For example, the first estimate of skew angle is determined by first obtaining a first set of points, wherein the first set of points comprises of image pixels first encountered when a set of parallel lines are traversed in a first direction from background pixels to image pixels. The first set of plural angles are derived from the first set of points by inverse tangent and the mean of the first set of plural angles may be used as the first estimate of the bitmap image skew angle. Thereafter, a standard deviation of the first set of plural angles is calculated and is the first reliability indicator of the first estimate of the skew angle. Similarly, the second, third and fourth estimates of the bitmap image skew angle may be calculated with corresponding reliability indicators.
As described above, the bitmap image is comprised of background and image pixels. The background pixels may be white and the image pixels may not all be white. Furthermore, the background pixels may be non-white and then the image pixels are of a different color than the background pixels.
Prior to determining the bitmap image skew angle, the bitmap image may be pre-processed by applying a filter, wherein the filter may be a median filter. Furthermore, to improve performance, the bitmap image may also be sub-sampled, prior to determining the bitmap image skew angle.
Some of the advantages of the first aspect of the invention are that it is not computationally intensive. Furthermore, the invention is equally effective with any type of image, text or graphics.
In another aspect, the invention auto-crops a bitmap image comprised of background and image pixels so that image pixels may be separated from background pixels. The first and last column of the bitmap image that is not all white is determined. Thereafter, the first and last row of the bitmap image that is not all white is determined. The first and last column, and the first and last row of pixels, which are not all white, define a rectangle. Finally the image is cropped by the defined rectangle.
The auto-cropped bitmap image comprises of background and image pixels. The background pixels may be white and the image pixels may not all be white. Furthermore, the background pixels may be non-white and then the image pixels are of a different color than the background pixels.
Prior to auto cropping the bitmap image, the image is de-skewed by a pre-determined bitmap image skew angle, as described above. Furthermore, prior to auto cropping, the bitmap image may also be pre-processed by applying a filter, wherein the filter may be a median filter and also sub-sampled for improving performance.
The second aspect of the invention automatically crops a bitmap image and hence separates the image pixels from the background pixels. The second aspect is also not computationally taxing and is highly accurate.
This brief summary has been provided so that the nature of the invention may be understood quickly. A more complete understanding of the invention can be obtained by reference to the following detailed description of the preferred embodiment thereof in connection with the attached drawings.